#include <iostream>
#include "BinaryTree.h"
using namespace std;

#include <iostream>
#include "BinaryTree.h"
using namespace std;

// BinarySearchTree test
void testBST() {
    BinarySearchTree<int> t;
    int NUMS = 400000;
    const int GAP = 3711;
    int i;

    cout << "BinarySearchTree testing..." << endl;

    for (i = GAP; i != 0; i = (i + GAP) % NUMS)
        t.insert(i);

    for (i = 1; i < NUMS; i += 2)
        t.remove(i);

    if (NUMS < 40)
        t.printTree();
    if (t.findMin() != 2 || t.findMax() != NUMS - 2)
        cout << "FindMin or FindMax error!" << endl;

    for (i = 2; i < NUMS; i += 2)
        if (!t.contains(i))
            cout << "Find error1!" << endl;

    for (i = 1; i < NUMS; i += 2) {
        if (t.contains(i))
            cout << "Find error2!" << endl;
    }

    BinarySearchTree<int> t2;
    t2 = t;

    for (i = 2; i < NUMS; i += 2)
        if (!t2.contains(i))
            cout << "Find error1!" << endl;

    for (i = 1; i < NUMS; i += 2) {
        if (t2.contains(i))
            cout << "Find error2!" << endl;
    }

    cout << "BinarySearchTree test completed." << endl;
}

// RedBlackTree test
void testRBT() {
    const int NEG_INF = -9999;
    RedBlackTree<int> t{ NEG_INF };
    int NUMS = 400000;
    const int GAP = 37;
    int i;

    cout << "RedBlackTree testing..." << endl;

    for (i = GAP; i != 0; i = (i + GAP) % NUMS)
        t.insert(i);

    if (NUMS < 40)
        t.printTree();
    if (t.findMin() != 1 || t.findMax() != NUMS - 1)
        cout << "FindMin or FindMax error!" << endl;

    for (i = 1; i < NUMS; ++i)
        if (!t.contains(i))
            cout << "Find error1!" << endl;
    if (t.contains(0))
        cout << "Oops!" << endl;

    RedBlackTree<int> t2{ NEG_INF };
    t2 = t;

    for (i = 1; i < NUMS; ++i)
        if (!t2.contains(i))
            cout << "Find error1!" << endl;
    if (t2.contains(0))
        cout << "Oops!" << endl;

    cout << "RedBlackTree test completed." << endl;
}

// SplayTree test
void testSplay() {
    SplayTree<int> t;
    int NUMS = 30000;
    const int GAP = 37;
    int i;

    cout << "SplayTree testing..." << endl;

    for (i = GAP; i != 0; i = (i + GAP) % NUMS)
        t.insert(i);

    for (i = 1; i < NUMS; i += 2)
        t.remove(i);

    if (NUMS < 40)
        t.printTree();
    if (t.findMin() != 2 || t.findMax() != NUMS - 2)
        cout << "FindMin or FindMax error!" << endl;

    for (i = 2; i < NUMS; i += 2)
        if (!t.contains(i))
            cout << "Find error1!" << endl;

    for (i = 1; i < NUMS; i += 2) {
        if (t.contains(i))
            cout << "Find error2!" << endl;
    }

    SplayTree<int> t2;
    t2 = t;

    for (i = 2; i < NUMS; i += 2)
        if (!t2.contains(i))
            cout << "Find error1!" << endl;

    for (i = 1; i < NUMS; i += 2) {
        if (t2.contains(i))
            cout << "Find error2!" << endl;
    }

    cout << "SplayTree test completed." << endl;
}

// AvlTree test
void testAVL() {
    AvlTree<int> t;
    int NUMS = 2000000;
    const int GAP = 37;
    int i;

    cout << "AvlTree testing..." << endl;

    for (i = GAP; i != 0; i = (i + GAP) % NUMS)
        t.insert(i);
    t.remove(0);
    for (i = 1; i < NUMS; i += 2)
        t.remove(i);

    if (NUMS < 40)
        t.printTree();
    if (t.findMin() != 2 || t.findMax() != NUMS - 2)
        cout << "FindMin or FindMax error!" << endl;

    for (i = 2; i < NUMS; i += 2)
        if (!t.contains(i))
            cout << "Find error1!" << endl;

    for (i = 1; i < NUMS; i += 2) {
        if (t.contains(i))
            cout << "Find error2!" << endl;
    }

    AvlTree<int> t2;
    t2 = t;

    for (i = 2; i < NUMS; i += 2)
        if (!t2.contains(i))
            cout << "Find error1!" << endl;

    for (i = 1; i < NUMS; i += 2) {
        if (t2.contains(i))
            cout << "Find error2!" << endl;
    }

    cout << "AvlTree test completed." << endl;
}

// main function
int main() {
    testBST();
    testRBT();
    testSplay();
    testAVL();
    return 0;
}
